package 堆结构常见题;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * @author ljb
 * @version 1.0
 * @Date 2024/11/24
 */
// 合并K个有序链表
// 测试链接：https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
//     https://leetcode.cn/problems/merge-k-sorted-lists/submissions/582771238/
public class Code01_MergeKSortedLists {
    public static class ListNode{
        public int val;
        public ListNode next;
    }

    /**
     * ArrayList<ListNode> arr 假如有k个已排好序的链表，arr中存的就是每条链表的头结点
     * @param arr
     * @return
     */
    public static ListNode mergeKLists(ArrayList<ListNode> arr){
        //小根堆
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : arr) {
            //遍历所有的头
            if(head != null){
                heap.add(head);
            }
        }
        if(heap.isEmpty()){
            return null;
        }
        //先弹出一个节点，做总头部
        ListNode head = heap.poll();
        ListNode pre = head;
        if(pre.next != null){
            heap.add(pre.next);
        }
        while(!heap.isEmpty()){
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = cur;
            if(cur.next != null){
                heap.add(cur.next);
            }
        }
        return head;
    }
}
